package com.leetcode.图论;

import java.util.*;

//课程表
public class lc_207 {
    public static void main(String[] args) {

    }

    /**
     * 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
     * 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，
     * 其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
     * 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
     **/
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //定义入度数组,索引处(课程号)对应入度,比如课程0的入度为0
        int[] inDegree = new int[numCourses];
        //定义map数组,key课程号,value: 依赖key的课程号, 比如key为1,以来的value为3,4
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < prerequisites.length; i++) {
            //遍历依赖关系表,在入度数组对应索引处++
            inDegree[prerequisites[i][0]]++;
            //没有对map初始化,这里对map初始化一个list数组,存放依赖的具体课程
            map.putIfAbsent(prerequisites[i][1], new ArrayList<>());
            //在对应被依赖课程key出添加依赖key的课程
            map.get(prerequisites[i][1]).add(prerequisites[i][1]);
        }

        //新建列表,把入度为0的课放进来
        Queue<Integer> que = new LinkedList<>();
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                que.offer(i);
            }
        }

        while (!que.isEmpty()) {
            //弹出已选课程,在map找到依赖它的课程,在入度数组--
            int course = que.poll();
            numCourses--;
            for (int nextCourse : map.getOrDefault(course, new ArrayList<>())) {
                if (--inDegree[nextCourse] == 0) {
                    que.offer(nextCourse);
                }
            }
        }
        return numCourses == 0;
    }
}
